home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / CONNECT4.ZIP / C4.INF < prev    next >
Text File  |  1997-05-17  |  12KB  |  248 lines
  1. /****************************************************************************/
  2. /**                                                                        **/
  3. /**                          Connect-4 Algorithm                           **/
  4. /**                                                                        **/
  5. /**                              Version 3.4                               **/
  6. /**                                                                        **/
  7. /**                            By Keith Pomakis                            **/
  8. /**                          (pomakis@pobox.com)                           **/
  9. /**                                                                        **/
  10. /**                              April, 1997                               **/
  11. /**                                                                        **/
  12. /****************************************************************************/
  13.  
  14. The files "c4.c" and "c4.h" provide the functions necessary to implement a
  15. front-end-independent, device-independent Connect-4 game.  Multiple board
  16. sizes are supported.  It is also possible to specify the number of pieces
  17. necessary to connect in a row in order to win.  Therefore one can play
  18. Connect-3, Connect-5, etc.  An efficient tree-searching algorithm (making
  19. use of alpha-beta cutoff decisions) has been implemented to insure that the
  20. computer plays as quickly as possible.
  21.  
  22. The file "game.c" is also being distributed, which illustrates how the
  23. Connect-4 functions can be used to construct an implementation of an actual
  24. game.  This file was quickly written just to get an actual implementation up
  25. and running; it is NOT the reason for this distribution.  The idea is for
  26. people to create their own front-ends for this algorithm.  The functions
  27. have been designed to be general enough to be used with any front-end one
  28. wishes to design.
  29.  
  30. The documentation describing each function can be found in the source code
  31. itself, "c4.c".  I believe the comments in this file are clear and
  32. explanatory enough not to warrant an external documentation file.  The
  33. sample front-end, "game.c", contains no documentation (hey, I've got other
  34. work to do, you know!).
  35.  
  36.  
  37. History
  38. -------
  39.  
  40. I developed this particular algorithm back in October 1992 for an
  41. Artificial Intelligence assignment.  At the time, I implemented it in LISP.
  42. One year later I decided to convert the algorithm to C code so that I could
  43. use it as the smarts of a graphical front-end to the game.  In performing
  44. the conversion, I took care to make the code as generic as possible.
  45.  
  46. Version 2.0 was released in March 1995 when John Tromp
  47. (tromp@daisy.uwaterloo.ca) pointed out to me that I was only implementing
  48. "shallow" alpha-beta cutoffs and showed me how to implement "deep" cutoffs.
  49. Thanks, John!
  50.  
  51. Version 2.1 (October, 1995) fixed a bug in the is_winner() function that
  52. occurred when the value of player was something other than 0 or 1.
  53.  
  54. Version 3.0 (November, 1995) was a complete overhaul.  Most of the guts
  55. remained the same, and it was just as efficient, but the interface
  56. functions changed.
  57.  
  58. Version 3.1 (May, 1996) fine-tuned some of the innards, making the average
  59. computer move take 1/3 of the time it used to.  Minor changes were made to
  60. the functional interface.
  61.  
  62. Version 3.2 (June, 1996) fine-tuned the innards a bit more, making it a
  63. bit more efficient.
  64.  
  65. Version 3.3 (November, 1996) fine-tuned the innards a bit more.  Also, the
  66. poll interval is now specified in terms of CPU time rather than tree depth.
  67. Thanks to Miles Michelson (milesmi@uclink4.berkeley.edu) for making this
  68. suggestion.
  69.  
  70. Version 3.4 (April, 1997) modified the order in which the game tree is
  71. searched, making the average computer move take 1/5 of the time it used
  72. to.  Thanks to William Krick (krick@elvis.rowan.edu) for suggesting this.
  73. Also fixed a bug that could be triggered when a board width or height
  74. smaller than the number of pieces required in a row to win is specified.
  75.  
  76.  
  77. Legal Stuff, etc.
  78. -----------------
  79.  
  80. I am releasing these functions to the public domain.  Therefore, people can
  81. use them, copy them, distribute them, modify them, and do whatever they
  82. want with them.
  83.  
  84. If you find any bugs (gasp!) or have any questions or comments about the
  85. functions or about the algorithm itself, you can contact me via e-mail.  My
  86. address is "pomakis@pobox.com".  I'd be interested in hearing what you think!
  87.  
  88. Oh, one other thing... I've put a lot of work into these functions, so I'd
  89. appreciate it if you kept my name attached to them when distributing or
  90. modifying them.  If you actually use these functions for anything, give me
  91. credit somewhere!
  92.  
  93.  
  94. The Algorithm  (not exactly as implemented, but algorithmically equivalent)
  95. -------------
  96.  
  97. All array indexes are zero-based.
  98.  
  99. Global variables:
  100.  
  101.               x = the board width.
  102.  
  103.               y = the board height.
  104.  
  105.               n = the number to connect.
  106.  
  107.        level[2] = the skill level of the computer players, where applicable.
  108.  
  109.     board[x][y] = the board, where board[i][j] contains the value:
  110.                         0 if player 0 occupies position i,j
  111.                         1 if player 1 occupies position i,j
  112.                         C4_NONE if neither player occupies position i,j.
  113.  
  114.               z = the number of possible n-in-a-row areas on the board
  115.                   in which a winning connection can be made.  This equals:
  116.                         4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2.
  117.  
  118.                   Each n-in-a-row area on the board in which a winning
  119.                   connection can be made is given a unique number from 0 to
  120.                   z-1.  Each space on the board is told which n-in-a-row
  121.                   areas it is part of.  This is done with the array...
  122.                   
  123.       map[x][y] = an array in which each element is a list specifying, for
  124.                   each corresponding board space, which n-in-a-row areas
  125.                   it is part of.
  126.  
  127.     stats[2][z] = an array containing statistics of each player.  Statistics
  128.                   for player 0 are contained in stats[0], while statistics
  129.                   for player 1 are contained in stats[1].  stats[a][b] will
  130.                   contain 0 if the n-in-a-row area b is no longer a
  131.                   winning possibility for player a.  Otherwise it will
  132.                   contain 2^p, where p is the number of pieces player a has
  133.                   in this area.
  134.  
  135. -----------------------------------------------------------------------------
  136.  
  137. Upper-level Algorithm:
  138.  
  139.     set every element in board[][] to C4_NONE
  140.     set every element in stats[][] to 1
  141.     set player to either 0 or 1
  142.  
  143.     while game is not over
  144.         col = get_desired_col(player)
  145.         drop_piece(player, col)
  146.  
  147.         if is_winner(player) or is_tie()
  148.             game is over
  149.         endif
  150.  
  151.         player = 1 - player
  152.     endwhile
  153.  
  154. -----------------------------------------------------------------------------
  155.  
  156. get_desired_col(player):
  157.     if player is human
  158.         return number from user interface
  159.     else
  160.         return best_move(player, level[player])
  161.     endif
  162.  
  163. -----------------------------------------------------------------------------
  164.  
  165. best_move(player, depth):  /* recursive! */
  166.     minimax search of possible future board states, using alpha-beta
  167.     cutoff techniques to limit unnecessary searches.  Look up these
  168.     techniques in any AI book.  The "goodness" of a board state at any
  169.     point in time, from the point of view of the current player, is equal to
  170.     score(player) - score(1-player), where score(p) = sum of stats[p].
  171.  
  172. -----------------------------------------------------------------------------
  173.  
  174. drop_piece(player, col):
  175.     row = row the token will end up in after falling down the column
  176.     board[col][row] = player
  177.     for each element q in map[col][row]
  178.         stats[player][q] = stats[player][q] * 2
  179.         stats[1-player][q] = 0
  180.     endfor
  181.  
  182. -----------------------------------------------------------------------------
  183.  
  184. is_winner(player):
  185.     for each element s in stats[player]
  186.         if s = 2^n then return TRUE
  187.     endfor
  188.     return FALSE
  189.  
  190. -----------------------------------------------------------------------------
  191.  
  192. is_tie():
  193.     if no element of board[][] is C4_NONE
  194.         return TRUE
  195.     else
  196.         return FALSE
  197.     endif
  198.  
  199. -----------------------------------------------------------------------------
  200.  
  201. sample map[x][y] for x = 6, y = 7, and n = 4:
  202.  
  203.     +---------+---------+---------+---------+---------+---------+---------+
  204.     |20,26,59 |20,21,29,|20,21,22,|20,21,22,|21,22,23,|22,23,41,|23,44,56 |
  205.     |         |62       |32,65    |23,35,47,|38,50    |53       |         |
  206.   5 |         |         |         |68       |         |         |         |
  207.     |         |         |         |         |         |         |         |
  208.     |         |         |         |         |         |         |         |
  209.     +---------+---------+---------+---------+---------+---------+---------+
  210.     |16,25,26,|16,17,28,|16,17,18,|16,17,18,|17,18,19,|18,19,40,|19,43,44,|
  211.     |58       |29,59,61 |31,32,47,|19,34,35,|37,38,49,|41,52,56 |55       |
  212.   4 |         |         |62,64    |46,50,65,|53,68    |         |         |
  213.     |         |         |         |67       |         |         |         |
  214.     |         |         |         |         |         |         |         |
  215.     +---------+---------+---------+---------+---------+---------+---------+
  216.     |12,24,25,|12,13,27,|12,13,14,|12,13,14,|13,14,15,|14,15,39,|15,42,43,|
  217.     |26,57    |28,29,47,|30,31,32,|15,33,34,|36,37,38,|40,41,51,|44,54    |
  218.   3 |         |58,60    |46,50,59,|35,45,49,|48,52,56,|55,68    |         |
  219.     |         |         |61,63    |53,62,64,|65,67    |         |         |
  220.     |         |         |         |66       |         |         |         |
  221.     +---------+---------+---------+---------+---------+---------+---------+
  222.     |8,24,25, |8,9,27,  |8,9,10,  |8,9,10,  |9,10,11, |10,11,39,|11,42,43,|
  223.     |26,47    |28,29,46,|30,31,32,|11,33,34,|36,37,38,|40,41,54,|44,68    |
  224.   2 |         |50,57    |45,49,53,|35,48,52,|51,55,62,|65,67    |         |
  225.     |         |         |58,60    |56,59,61,|64,66    |         |         |
  226.     |         |         |         |63       |         |         |         |
  227.     +---------+---------+---------+---------+---------+---------+---------+
  228.     |4,24,25, |4,5,27,  |4,5,6,30,|4,5,6,7, |5,6,7,36,|6,7,39,  |7,42,43, |
  229.     |46       |28,45,49 |31,48,52,|33,34,51,|37,54,61,|40,64,66 |67       |
  230.   1 |         |         |57       |55,58,60 |63       |         |         |
  231.     |         |         |         |         |         |         |         |
  232.     |         |         |         |         |         |         |         |
  233.     +---------+---------+---------+---------+---------+---------+---------+
  234.     |0,24,45  |0,1,27,  |0,1,2,30,|0,1,2,3, |1,2,3,36,|2,3,39,63|3,42,66  |
  235.     |         |48       |51       |33,54,57 |60       |         |         |
  236.   0 |         |         |         |         |         |         |         |
  237.     |         |         |         |         |         |         |         |
  238.     |         |         |         |         |         |         |         |
  239.     +---------+---------+---------+---------+---------+---------+---------+
  240.  
  241.          0         1         2         3         4         5         6
  242.  
  243.  0 - 23: horizontal wins
  244. 24 - 44: vertical wins
  245. 45 - 56: forward diagonal wins
  246. 57 - 68: backward diagonal wins
  247.  
  248.